package main

func main() {
	grids := [][]byte{
		{1, 1, 0, 0, 0},
		{1, 1, 0, 0, 0},
		{0, 0, 1, 0, 0},
		{0, 0, 0, 1, 1}}
	res := numIslands(grids)
	println(res)
}

//200. 岛屿数量
func numIslands(grid [][]byte) int {
	var res int
	if len(grid) == 0 || len(grid[0]) == 0 {
		return res
	}
	height := len(grid)
	width := len(grid[0])

	for i := 0; i < height; i++ {
		for j := 0; j < width; j++ {
			if grid[i][j] == 1 {
				res++
				dfs(grid, i, j)
			}
		}
	}

	return res
}

// 使用递归的方式查询

func dfs(grid [][]byte, row, column int) {
	if len(grid) == 0 || len(grid[0]) == 0 {
		return
	}
	height := len(grid) - 1
	width := len(grid[0]) - 1
	if row < 0 || column < 0 || row > height || column > width || grid[row][column] == 0 {
		return
	}
	grid[row][column] = 0
	dfs(grid, row-1, column)
	dfs(grid, row+1, column)
	dfs(grid, row, column-1)
	dfs(grid, row, column+1)
}

// 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
//
//岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
//
//此外，你可以假设该网格的四条边均被水包围。
//
//
//
//示例 1：
//
//输入：grid = [
//  ["1","1","1","1","0"],
//  ["1","1","0","1","0"],
//  ["1","1","0","0","0"],
//  ["0","0","0","0","0"]
//]
//输出：1
//示例 2：
//
//输入：grid = [
//  ["1","1","0","0","0"],
//  ["1","1","0","0","0"],
//  ["0","0","1","0","0"],
//  ["0","0","0","1","1"]
//]
//输出：3
//
//
//提示：
//
//m == grid.length
//n == grid[i].length
//1 <= m, n <= 300
//grid[i][j] 的值为 '0' 或 '1'
